from typing import List


class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        # 寻找最大上界
        bit = max(nums).bit_length()
        cache = [0] * pow(2, bit)
        mask = pow(2, bit) - 1

        # 计算与每一个数与为零的数
        for num in nums:
            val = mask ^ num
            i = val
            while i > 0:
                cache[i] += 1
                i = (i - 1) & val
            cache[i] += 1

        ans = 0
        for n1 in nums:
            for n2 in nums:
                ans += cache[n1 & n2]
        return ans


if __name__ == "__main__":
    print(Solution().countTriplets([2, 1, 3]))  # 12
